# coding: utf-8
# 堆排序实现（这里是大根堆/大顶堆）
# 图解堆排序：https://www.cnblogs.com/chengxiao/p/6129630.html
# 堆的下标：已知节点i，左叶子节点2i+1，右叶子节点2i+2；已经叶子节点i，父节点(i-1)/2取整。
# 堆的基本操作：交换、向下调整shiftDown、向上调整shiftUp、构建堆buildHeap
# 注意区别堆的调整和构建：堆的构建是从非叶子结点、从下往上、从右往左！
# 堆排序：构建大根堆，取走根（最大的元素），重复从上往下调整的步骤。

#大顶堆就是一个优先队列，出队方法pop
class MaxHeap:
    def __init__(self,initList):
        self.data=initList
        self.length=len(initList)

    def __repr__(self):
        return "MaxHeap[length={length},data={data}]".format(length=self.length, data=self.data)

    #计算左孩子的位置
    def lchild(self,pos):
        return 2*pos+1

    #计算右孩子的位置
    def rchild(self,pos):
        return 2*pos+2

    #计算父节点的位置
    def parent(self,pos):
        return int((pos-1)/2)

    #核心方法：往下调整一个元素
    def shiftDown(self,pos,len):
        if pos<0 or pos>=len:
            raise Exception("越界了 pos={pos}".format(pos=pos))
        val=self.data[pos]

        child=self.lchild(pos)
        while child<len:
            #取左右叶子节点中比较大的节点
            rchild=self.rchild(pos)
            if rchild<len and self.data[rchild]>self.data[child]:
                child=rchild
            if self.data[child]>val:
                self.data[pos]=self.data[child]
                pos=child
                #下一层调整
                child=self.lchild(pos)
            else:
                break
        #最终放置的位置
        self.data[pos]=val

    #shiftDown递归写法 比循环简单
    def shiftDownR(self,pos,len):
        if pos<0 or pos>=len:
            raise Exception("越界了 pos={pos}".format(pos=pos))
        val=self.data[pos]

        child=self.lchild(pos)
        if child>=len:
            return

        rchild=self.rchild(pos)
        if rchild<len and self.data[rchild]>self.data[child]:
            child=rchild

        if self.data[child]<=val:
            return
        
        self.data[pos],self.data[child]=self.data[child],self.data[pos]
        self.shiftDownR(child,len)

    #往上调整一个元素
    def shiftUp(self,pos):
        val=self.data[pos]
        pa = self.parent(pos)
        while pa>=0 and self.data[pa]<self.data[pos]:
            self.data[pos]=self.data[pa]
            pos=pa
            #上一层
            pa=self.parent(pos)
        self.data[pos]=val

    #shiftUp递归写法 比循环简单
    def shiftUpR(self,pos):
        pa = self.parent(pos)
        if pa>=0 and self.data[pa]<self.data[pos]:
            self.data[pa],self.data[pos]=self.data[pos],self.data[pa]
            self.shiftUpR(pa)

    #插入元素
    def add(self,item):
        self.data.append(item)
        self.length+=1
        self.shiftUpR(self.length-1)

    #弹出根元素(最大的元素)
    def pop(self):
        if self.length<=0:
            return None
        if self.length<=1:
            self.length-=1
            return self.data.pop(0)

        val=self.data[0]
        self.data[0]=self.data[self.length-1]
        self.data.pop(self.length-1)
        self.length-=1
        self.shiftDown(0,self.length)

        return val
    
    def buildHeap(self):
        #从第一个非叶子节点开始
        i=self.parent(self.length-1)
        while i>=0:
            self.shiftDown(i,self.length)
            i-=1

    def heapSort(self):
        self.buildHeap()
        for i in range(self.length-1,0,-1):
            self.data[0],self.data[i]=self.data[i],self.data[0]
            self.shiftDownR(0,i)

    def heapSort2(self):
        temp=[]
        self.buildHeap()
        while self.length>0:
            temp.append(self.pop())
        temp=temp[::-1]
        self.data=temp
        self.length=len(temp)
    
heap=MaxHeap([1,11,2,22,3,33])
heap.heapSort()
# heap.buildHeap()
# heap.add(100)
print(heap)
